// https://www.lintcode.com/problem/copy-list-with-random-pointer/

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        /*
        思路如下，abcd...代表原链表，a'b'c'd'...代表新链表。()内代表random，'/'代表None。
        初始状态：a(d)->b(/)->c(e)->d(a)
        1. 插入并复制原来的random节点：a(d)->a'(d)->b(/)->b'(/)->c(e)->c'(e)->d(a)->d'(a)
        2. 更新新节点的random（因为x指向x'）：a(d)->a'(d')->b(/)->b'(/)->c(e)->c'(e')->d(a)->d'(a')
        3. 拆成两条链表并返回
        */
        if (head == null) {
            return null;
        }
        RandomListNode node = head;
        while (node != null) {
            RandomListNode newNode = new RandomListNode(node.label);
            newNode.next = node.next;
            newNode.random = node.random;
            node.next = newNode;
            node = newNode.next;
        }
        node = head.next;
        while (node != null) {            
            if (node.random != null) {
                node.random = node.random.next;
            }
            node = node.next;
            if (node != null) {
                node = node.next;
            }
        }
        RandomListNode newHead = null;
        RandomListNode newTail = null;
        node = head;
        while (node != null) {
            RandomListNode nextNode = node.next;
            node.next = nextNode.next; // 长度为偶数，不用校验是否为null
            
            node = node.next;
            if (newHead == null) {
                newHead = nextNode;
            } else {
                newTail.next = nextNode;
            }
            newTail = nextNode;
            newTail.next = null;
        }
        return newHead;
    }
}